Where to Build a Brewery?

Memory limit: 32 MB

The dwellers of the island Abstinence are very fond of alkoholfree beer. Hitherto alkohol-free beer was imported from Poland, but this year one of the cities on Abstinence is going to build a brewery. All the cities of this island lie on the coast and are connected by a highway running around the island along its shore. The investor building the brewery collected information about the demand for beer, i.e. how many tanks of beer are needed daily in each city. He has also a table of distances between cities. The cost of transporting one tank is 1 thaler per mile. A daily cost of transport is the amount of money, which has to be spent on transporting a necessary number of tanks of beer from the brewery to each city. The daily cost depends on the location of the brewery. The investor wants to find a location that minimizes the daily cost.

Task

Write a program which

• reads the number of cities, distances between them and daily requests for beer,
• computes the minimal daily cost of transport,
• writes the result to the standard output.

Input

In the first line of the standard input there is one integer - the number of cities, . (We assume that cities are numbered along the highway, so that the neighbouring cities have subsequent numbers. Cities 1 and are neighbours too.) In each of the following lines there are two non-negative numbers separated by a single space. Numbers , written in the line () are respectively the demand for beer in the city and the distance (in miles) from city to the next city on the highway. The entire length of the highway is not greater than miles. The demand for beer in each city is not greater than tanks.

Output

Your program should write in the first and only line of the standard output exactly one integer equal to the minimal daily cost of transport.

Example

For the input data:

6
1 2
2 3
1 2
5 2
1 10
2 3

the correct result is:

41

Task author: Wojciech Guzicki.